МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ КОДІВ ХЕМІНГА ІНСТРУКЦІЯ до лабораторної роботи № 1 з курсу “ Основи збору, передачі та обробки інформації” для студентів базового напряму 6.1601 “Захист інформації” Затверджено на засiданнi кафедри "Захист інформації" Протокол N вiд . .2007 p. Львів 2007 Дослідження кодоутворення та принципів побудови кодерів і декодерів кодів Хемінга: Інструкція до лабораторної роботи № 1 з курсів «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Захист інформації» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, В. І. Отенко, Я. Р. Совин. – Львів: НУЛП, 2007. – 13 с. Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., В. І. Отенко, канд. техн. наук, доц., Я. Р. Совин, асист. Відповідальний за випуск М. В. Кіріанакі, канд. техн. наук, доц. Рецензенти: З. Р. Мичуда, канд. техн. наук, доц., О. В. Івахів, канд. техн. наук, доц. Складання і відлагодження схеми здійснено асист. каф. захисту інформації Совином Я. Р. мета роботи – вивчити принципи побудови кодів Хемінга та одержати практичні навики розробки функціональних схем кодерів і декодерів. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Простота реалізації та ефективне забезпечення завадостійкості зумовили широке застосування коду Хемінга (КХ) не лише у телемеханіці, але і в обчислювальній техніці та зв’язку. Відомі декілька різновидностей КХ, які характеризуються різною коректуючою здатністю [1, 2]. Код Хемінга з d = 3 забезпечує виявлення двократних (r = 2) або виправлення однократної (S = 1) помилки, оскільки d = r + 1 або d = 2S + 1. Вихідним для коду Хемінга є первинний (двійковий або двійково-десятковий)
-розрядний код, до якого в результаті вторинного кодування додають
контрольних розрядів. Отже, загальна довжина кодової комбінації (КК) збільшиться до
. Кількість робочих комбінацій
. Число контрольних розрядів знаходять із виразу [2, 3]:
(1) В табл. 1 наведені значення п і
, для різних
, що задовільняють умову (1). Таблиця 1
3 4 5 6 7 8  п 7 15 31 63 127 255  
4 11 26 57 120 247   Оскільки при збільшенні кількості інформаційних розрядів
, кількість контрольних розрядів
зростає незначно, надлишковість коду,
(2) зменшується, а швидкість передачі інформації
(3) зростає. Побудова коду Хемінга, що виправляє всі одиничні помилки (d = 3) здійснюється так. Спочатку визначають необхідну кількість контрольних розрядів на підставі співвідношення (1). Далі визначають їх розташування в кодовій комбінації. Для спрощення кодування і декодування контрольні символи розташовують на місцях КК, кратних степеню 2, тобто на позиціях 1, 2, 4, 8, 16 і т.д., хоча їх розташування може бути довільним. Інформаційні розряди розташовуються на вільних місцях. На основі зазначеного для 15-розрядної кодової комбінації можна записати:
де І3 перший (молодший), а І15 одинадцятий (старший) розряд робочої (інформаційної) КК. У циклічному коді Хемінга контрольні символи розташовуються після інформаційних розрядів [4]. Потім знаходять значення контрольних символів (0 або 1) підсумовуючи за модулем два (перевірка на парність) значення певних інформаційних розрядів за алгоритмом Хемінга так:
. (4)
; (5)
; (6)
; (7) Щоб виключити необхідність багатократного використання цих рівнянь для визначення контрольних символів, для кожної із
робочих КК застосовують так звану утворюючу м...